package com.da.javatest.leetCode;

/**
 * @author chenlida
 * @date 2018/12/21 17:16
 * @description
 */
public class Code109 {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(-10);
        ListNode l2 = new ListNode(-3);
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(5);
        ListNode l5 = new ListNode(9);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        new Code109().sortedListToBST(l1);
    }

    public TreeNode sortedListToBST(ListNode head) {
        // 左右等分建立左右子树，中间节点作为子树根节点，递归该过程
        if (head == null) {
            return null;
        }
        return buildTree(head, 0, getNodeLength(head, 0) - 1);
    }

    private TreeNode buildTree(ListNode head, int l, int r) {
        if (l > r) {
            return null;
        }
        if (l == r) {
            return new TreeNode(getNodeVal(head, 0, l));
        }
        int mid = (l + r) / 2;
        TreeNode root = new TreeNode(getNodeVal(head, 0, mid));
        root.left = buildTree(head, l, mid - 1);
        root.right = buildTree(head, mid + 1, r);
        return root;
    }

    private int getNodeVal(ListNode head, int start, int end) {
        if (head == null) {
            return 0;
        }
        if (start == end) {
            return head.val;
        } else {
            return getNodeVal(head.next, start += 1, end);
        }
    }

    private int getNodeLength(ListNode head, int start) {
        if (head == null) {
            return start;
        } else {
            return getNodeLength(head.next, start += 1);
        }
    }
}
